package freedom;

/**
 * @author caifangyi
 * @date 2022/7/22
 */

import java.util.Arrays;

/**
 * 仓库有货物，每个货物重n顿，现在需要按一定顺序进行运输，假如运输k次，选择最大运输为几顿的船合适？
 */
class F001_小船送货 {

    public static void main(String[] args) {
        int[] nums = {1,2,3,6,1};
        Solution solution = new Solution();
        int search = solution.search(nums, 2);
        System.out.println(search);

    }

    static class Solution{

        public int search(int[] nums, int target){

            //先求出货物最大值和总值，然后进行二分
            int max = Arrays.stream(nums).max().getAsInt();
            int sum = Arrays.stream(nums).sum();

            //构造k的数组
            int[] kArr = new int[sum-max+1];

            int i = 0;
            int bound = max;
            while (bound <= sum){
                kArr[i] = getK(nums, bound);
                bound++;
                i++;
            }

            int i1 = binarySearchFirst(kArr, 2);
            return max+i1;
        }

        private int getK(int[] nums, int w){
            int count = 0;
            int i = 0;
            int sum = 0;
            while(i<nums.length-1){
                sum += nums[i];
                if(sum+nums[i+1] > w){
                    count++;
                    sum = 0;
                }
                i++;
            }
            return ++count;
        }

        private int binarySearchFirst(int nums[], int target){
            int l = 0;
            int r = nums.length - 1;
            while(l < r){
                int mid = (l+r) >> 1;
                if(nums[mid] <= target){
                    r = mid;
                }else{
                    l = mid +1;
                }
            }
            return l;
        }

    }
}
